package com.gitee.feizns.explore.data_structure.sort;

import java.util.Arrays;

/**
 * @author feizns
 * @since 2020/1/3
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = { 1,1,1,1,1 };
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int l, int r) {
        if ( l >= r ) return;
        final int[] ints = partition4(arr, l, r);
        quickSort(arr, l, ints[0]);
        quickSort(arr, ints[1], r);
    }

    private static int partition(int[] arr, int l, int r) {
        int p = (int) ((Math.random() * (r - l + 1)) + l);
        swap(arr, l, p);
        int v = arr[l];
        int i = l;
        for (int j = l + 1; j <= r; j++) {
            if ( arr[j] < v )
                swap(arr, ++i, j);
        }
        swap(arr, l, i);
        return i;
    }

    private static int partition2(int[] arr, int l, int r) {
        int p = (int) ((Math.random() * (r - l + 1)) + l);
        swap(arr, l, p);
        int v = arr[l];
        int i = l + 1;
        int j = r;
        while ( true ) {
            while ( i <= r && arr[i] < v ) { i++; }
            while ( j >= l + 1 && arr[j] > v ) { j--; }
            if ( i >= j )
                break;
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

    private static int partition3(int[] arr, int l, int r) {
        int p = (int) ((Math.random() * (r - l + 1)) + l);
        swap(arr, l, p);
        int v = arr[l];
        int lw = l;
        int i = l + 1;
        int g = r + 1;
        while ( i < g ) {
            if ( arr[i] < v ) {
                swap(arr, lw + 1, i);
                i++;
                lw++;
            } else if ( arr[i] > v ) {
                g--;
            } else {
                i++;
            }
        }
        return i;
    }

    public static int[] partition4(int[] arr, int l , int r) {
        int p = (int) (Math.random() * (r - l + 1)) + l;
        swap(arr, l, p);
        int v = arr[l];
        int lw = l;
        int i = l + 1;
        int g = r + 1;
        while ( i < g ) {
            if ( arr[i] > v ) {
                swap(arr, i, g - 1);
                g--;
            } else {
                if ( arr[i] < v ) {
                    swap(arr, i, lw + 1);
                    lw++;
                }
                i++;
            }
        }
        swap(arr, l, lw);
        return new int[]{lw, g };
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
